<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-CN">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />




  
  
  
  

  
    
    
  

  
    
      
    

    
  

  
    
      
    

    
  

  
    
      
    

    
  

  
    
      
    

    
  

  
    
    
    <link href="//fonts.googleapis.com/css?family=Microsoft YaHei:300,300italic,400,400italic,700,700italic|Microsoft YaHei:300,300italic,400,400italic,700,700italic|Microsoft YaHei:300,300italic,400,400italic,700,700italic|Microsoft YaHei:300,300italic,400,400italic,700,700italic|Inziu Iosevka Slab SC:300,300italic,400,400italic,700,700italic&subset=latin,latin-ext" rel="stylesheet" type="text/css">
  






<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.2" rel="stylesheet" type="text/css" />


  <meta name="keywords" content="Hexo, NexT" />








  <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico?v=5.1.2" />






<meta name="description" content="Apriori is an algorithm for frequent item set mining and association rule learning over transactional databases. It proceeds by identifying the frequent individual items in the database and extending">
<meta property="og:type" content="article">
<meta property="og:title" content="Apriori Algorithm">
<meta property="og:url" content="http://idmk.oschina.io/2017/08/29/Apriori-algorithm/index.html">
<meta property="og:site_name" content="苦舟">
<meta property="og:description" content="Apriori is an algorithm for frequent item set mining and association rule learning over transactional databases. It proceeds by identifying the frequent individual items in the database and extending">
<meta property="og:locale" content="zh-CN">
<meta property="og:image" content="http://idmk.oschina.io/2017/08/29/Apriori-algorithm/markdown-img-paste-20170829133420417.png">
<meta property="og:updated_time" content="2017-11-22T15:33:53.594Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Apriori Algorithm">
<meta name="twitter:description" content="Apriori is an algorithm for frequent item set mining and association rule learning over transactional databases. It proceeds by identifying the frequent individual items in the database and extending">
<meta name="twitter:image" content="http://idmk.oschina.io/2017/08/29/Apriori-algorithm/markdown-img-paste-20170829133420417.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    sidebar: {"position":"left","display":"hide","offset":12,"offset_float":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: true,
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://idmk.oschina.io/2017/08/29/Apriori-algorithm/"/>





  <title>Apriori Algorithm | 苦舟</title>
  














</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-CN">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail ">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">苦舟</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">学海无涯，吾将上下求索。</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br />
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-commonweal">
          <a href="/404.html" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-heartbeat"></i> <br />
            
            公益404
          </a>
        </li>
      

      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br />
            
            搜索
          </a>
        </li>
      
    </ul>
  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off"
             placeholder="搜索..." spellcheck="false"
             type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://idmk.oschina.io/2017/08/29/Apriori-algorithm/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="东木金">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/uploads/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="苦舟">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">Apriori Algorithm</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-08-29T10:39:18+08:00">
                2017-08-29
              </time>
            

            

            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/ML/" itemprop="url" rel="index">
                    <span itemprop="name">ML</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>Apriori is an algorithm for frequent item set mining and association rule learning over transactional databases. It proceeds by identifying the frequent individual items in the database and extending them to larger and larger item sets as long as those item sets appear sufficiently often in the database. The frequent item sets determined by Apriori can be used to determine association rules which highlight general trends in the database: this has applications in domains such as market basket analysis.</p>
<a id="more"></a>
<p>Looking for hidden relationships in large datasets is known as association analysis or association rule learning. Frequent item sets are a collection of items that frequently occur together. Association rules suggest that a strong relationship exists between two items. Frequent items sets are lists of items that commonly appear together.</p>
<p>An association rule – diapers ➞ wine means that if someone buys diapers, there ’ s a good chance they ’ ll buy wine.</p>
<p>How do we define these so-called interesting relationships? Who defines what ’ s interesting? When we ’ re looking for frequent item sets, what ’ s the definition of frequent? There are a number of concepts we can use to select these things, but the two most important are support and confidence.</p>
<p>The support of an itemset is defined as the percentage of the dataset that containsthis itemset. For example, the support of {soy milk, diapers} is 3/5 because of five transactions, three contained both soy milk and diapers.<br>The confidence is defined for an association rule like {diapers} –&gt; {wine}. The confidence for this rule is defined as support({diapers, wine})/support({diapers}). The support and confidence are ways we can quantify the success of our association analysis.</p>
<h2 id="The-Apriori-principle"><a href="#The-Apriori-principle" class="headerlink" title="The Apriori principle"></a>The Apriori principle</h2><p>Let ’ s assume we wanted to find all sets of items with a support greater than 0.8. How would we do that? We could generate a list of every combination of items and then count how frequently that occurs. It turns out that doing this can be very slow when we have thousands of items for sale. the Apriori principle is introduced, which will allow us to reduce the number of calculations we need to do to learn association rules.</p>
<p>The Apriori principle helps us reduce the number of possible interesting itemsets. The Apriori principle says that if an itemset is frequent, then all of its subsets are frequent. This rule as it is doesn ’ t help us, but if we turn it inside out, it will help us. The rule turned around says that if an itemset is infrequent, then its supersets are also infrequent.</p>
<blockquote>
<p>Apriori<br>A priori means “ from before ” in Latin. When defining a problem, it ’ s common to state prior knowledge, or assumptions. This is written as “ a priori. ” In Bayesian statistics, it ’ s common to make inferences conditional upon this a priori knowledge. A priori knowledge can come from domain knowledge, previous measurements, and so on.</p>
</blockquote>
<img src="/2017/08/29/Apriori-algorithm/markdown-img-paste-20170829133420417.png" alt="Figure 1" title="Figure 1">
<p>All possible itemsets shown, with infrequent itemsets shaded in gray. With the knowledge that the set {2,3} is infrequent, we can deduce that {0,2,3}, {1,2,3}, and {0,1,2,3} are also infrequent, and we don ’ t need to compute their support.</p>
<h2 id="Finding-frequent-itemsets-with-the-Apriori-algorithm"><a href="#Finding-frequent-itemsets-with-the-Apriori-algorithm" class="headerlink" title="Finding frequent itemsets with the Apriori algorithm"></a>Finding frequent itemsets with the Apriori algorithm</h2><p>We first need to find the frequent itemsets, and then we can find association rules. In this section, we ’ ll focus only on finding the frequent itemsets.</p>
<p>The way to find frequent itemsets is the Apriori algorithm. The Apriori algorithm needs a minimum support level as an input and a data set. The algorithm will generate a list of all candidate itemsets with one item. The transaction data set will then be scanned to see which sets meet the minimum support level. Sets that don ’ t meet the minimum support level will get tossed out. The remaining sets will then be combined to make itemsets with two elements. Again, the transaction dataset will be scanned and itemsets not meeting the minimum support level will get tossed. This procedure will be repeated until all sets are tossed out.<br>从原子项开始，筛选出支持度过小的项；两两组装成新的项，再筛选出支持度过小的项；重复上面的步骤，直到剩下的项为空。</p>
<h3 id="Generating-candidate-itemsets"><a href="#Generating-candidate-itemsets" class="headerlink" title="Generating candidate itemsets"></a>Generating candidate itemsets</h3><p>we ’ ll need to create a few helper functions. We ’ ll create a function to create an initial set, and we ’ ll create a function to scan the dataset looking for items that are subsets of transactions. Pseudocode for scanning the dataset would look like this:</p>
<pre><code>For each transaction, tran in the dataset:
    For each candidate itemset, can:
        Check to see if can is a subset of tran
        If so increment the count of can
    For each candidate itemset:
    If the support meets the minimum, keep this item Return list of frequent itemsets
</code></pre><h4 id="代码实现"><a href="#代码实现" class="headerlink" title="代码实现"></a>代码实现</h4><figure class="highlight python"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">load_dataset</span><span class="params">()</span>:</span></div><div class="line">    <span class="keyword">return</span> [[<span class="number">1</span>, <span class="number">3</span>, <span class="number">4</span>], [<span class="number">2</span>, <span class="number">3</span>, <span class="number">5</span>], [<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">5</span>], [<span class="number">2</span>, <span class="number">5</span>]]</div><div class="line">    <span class="comment"># transaction list</span></div><div class="line">    <span class="comment"># transaction is item list</span></div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">create_c1</span><span class="params">(X)</span>:</span></div><div class="line">    <span class="comment"># C1 is a candidate itemset ofsize one.</span></div><div class="line">    C1 = []</div><div class="line">    <span class="keyword">for</span> tran <span class="keyword">in</span> X:</div><div class="line">        <span class="keyword">for</span> item <span class="keyword">in</span> tran:</div><div class="line">            <span class="keyword">if</span> <span class="keyword">not</span> [item] <span class="keyword">in</span> C1:</div><div class="line">                C1.append([item])</div><div class="line">    C1.sort()</div><div class="line">    <span class="keyword">return</span> list(map(frozenset, C1))</div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">test01</span><span class="params">()</span>:</span></div><div class="line">    X = load_dataset()</div><div class="line">    C1 = create_c1(X)</div><div class="line">    print(C1)</div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">scan_dataset</span><span class="params">(X, Ck, min_support)</span>:</span></div><div class="line">    ss_cnt = &#123;&#125;</div><div class="line">    <span class="keyword">for</span> tid <span class="keyword">in</span> X:</div><div class="line">        <span class="keyword">for</span> can <span class="keyword">in</span> Ck:</div><div class="line">            <span class="keyword">if</span> can.issubset(tid):</div><div class="line">                ss_cnt[can] = ss_cnt.get(can, <span class="number">0</span>) + <span class="number">1</span></div><div class="line">    n_items = len(X)</div><div class="line">    freq_item_list = []</div><div class="line">    support_data = &#123;&#125;</div><div class="line">    <span class="keyword">for</span> can <span class="keyword">in</span> ss_cnt:</div><div class="line">        support = ss_cnt[can] / n_items</div><div class="line">        <span class="keyword">if</span> support &gt;= min_support:</div><div class="line">            freq_item_list.insert(<span class="number">0</span>, can)</div><div class="line">        support_data[can] = support</div><div class="line">    <span class="keyword">return</span> freq_item_list, support_data</div></pre></td></tr></table></figure>
<p>说明：<br>The function createC1() creates C1. C1 is a candidate itemset ofsize one.<br>The function scan_dataset scan the dataset to see if these one itemsets meet our minimum support requirements. The itemsets that do meet our minimum requirements become L1. L1 then gets combined to become C2 and C2 will get filtered to become L2.</p>
<h2 id="the-full-Apriori-algorithm"><a href="#the-full-Apriori-algorithm" class="headerlink" title="the full Apriori algorithm"></a>the full Apriori algorithm</h2><p>Pseudo-code for the whole Apriori algorithm would look like this:</p>
<pre><code>While the number of items in the set is greater than 0:
    Create a list of candidate itemsets of length k
    Scan the dataset to see if each itemset is frequent
    Keep frequent itemsets to create itemsets of length k+1
</code></pre><p>Now that you can filter out sets, it ’ s time to build the full Apriori algorithm. Open apriori.py and add the code from the following listing.</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">load_dataset</span><span class="params">()</span>:</span></div><div class="line">    <span class="keyword">return</span> [[<span class="number">1</span>, <span class="number">3</span>, <span class="number">4</span>], [<span class="number">2</span>, <span class="number">3</span>, <span class="number">5</span>], [<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">5</span>], [<span class="number">2</span>, <span class="number">5</span>]]</div><div class="line">    <span class="comment"># transaction list</span></div><div class="line">    <span class="comment"># transaction is item list</span></div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">create_c1</span><span class="params">(X)</span>:</span></div><div class="line">    <span class="comment"># C1 is a candidate itemset ofsize one.</span></div><div class="line">    C1 = []</div><div class="line">    <span class="keyword">for</span> tran <span class="keyword">in</span> X:</div><div class="line">        <span class="keyword">for</span> item <span class="keyword">in</span> tran:</div><div class="line">            <span class="keyword">if</span> <span class="keyword">not</span> [item] <span class="keyword">in</span> C1:</div><div class="line">                C1.append([item])</div><div class="line">    C1.sort()</div><div class="line">    <span class="keyword">return</span> list(map(frozenset, C1))</div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">scan_dataset</span><span class="params">(X, Ck, min_support)</span>:</span></div><div class="line">    ss_cnt = &#123;&#125;</div><div class="line">    <span class="keyword">for</span> tid <span class="keyword">in</span> X:</div><div class="line">        <span class="keyword">for</span> can <span class="keyword">in</span> Ck:</div><div class="line">            <span class="keyword">if</span> can.issubset(tid):  <span class="comment"># tid 被自动转化为 set 类型</span></div><div class="line">                ss_cnt[can] = ss_cnt.get(can, <span class="number">0</span>) + <span class="number">1</span></div><div class="line">    n_items = len(X)</div><div class="line">    freq_item_list = []</div><div class="line">    support_data = &#123;&#125;</div><div class="line">    <span class="keyword">for</span> can <span class="keyword">in</span> ss_cnt:</div><div class="line">        support = ss_cnt[can] / n_items</div><div class="line">        <span class="keyword">if</span> support &gt;= min_support:</div><div class="line">            freq_item_list.insert(<span class="number">0</span>, can)</div><div class="line">        support_data[can] = support</div><div class="line">    <span class="keyword">return</span> freq_item_list, support_data</div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">apriori_gen</span><span class="params">(Lk, k)</span>:</span>  <span class="comment"># creates Ck。 Ck 包含 k 个项的集合，Lk 从 Ck 中提取出的频繁项集</span></div><div class="line">    ret_list = []</div><div class="line">    len_Lk = len(Lk)</div><div class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(len_Lk):</div><div class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> range(i + <span class="number">1</span>, len_Lk):</div><div class="line">            <span class="comment"># L1 = list(Lk[i])[:k-2]</span></div><div class="line">            <span class="comment"># L2 = list(Lk[j])[:k-2]</span></div><div class="line">            print(Lk[i])</div><div class="line">            print(Lk[j])</div><div class="line">            L1 = list(Lk[i])[:k<span class="number">-2</span>]</div><div class="line">            L2 = list(Lk[j])[:k<span class="number">-2</span>]</div><div class="line">            L1.sort()</div><div class="line">            L2.sort()</div><div class="line">            print()</div><div class="line">            <span class="keyword">if</span> L1 == L2:</div><div class="line">                ret_list.append(Lk[i] | Lk[j])</div><div class="line">    <span class="keyword">return</span> ret_list</div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">apriori</span><span class="params">(X, min_support=<span class="number">0.5</span>)</span>:</span></div><div class="line">    C1 = create_c1(X)</div><div class="line">    L1, support_data = scan_dataset(X, C1, min_support)</div><div class="line">    L = [L1]</div><div class="line">    k = <span class="number">2</span></div><div class="line">    <span class="keyword">while</span> (len(L[k<span class="number">-2</span>]) &gt; <span class="number">0</span>):</div><div class="line">        Ck = apriori_gen(L[k - <span class="number">2</span>], k)</div><div class="line">        Lk, support_k = scan_dataset(X, Ck, min_support)</div><div class="line">        support_data.update(support_k)</div><div class="line">        L.append(Lk)</div><div class="line">        k += <span class="number">1</span></div><div class="line">    <span class="keyword">return</span> L, support_data</div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">test03</span><span class="params">()</span>:</span></div><div class="line">    X = load_dataset()</div><div class="line">    L, support_data = apriori(X)</div><div class="line"></div><div class="line"></div><div class="line"><span class="keyword">if</span> __name__ == <span class="string">"__main__"</span>:</div><div class="line">    test03()</div></pre></td></tr></table></figure>
<p>说明：<br>频繁项集：支持都大于阈值的项集。</p>
<p>Ck：长度为 k     表示交易集合中出现的单个项的集合；Ck 表示长度为 k 的项集组成的列表，其中长度为 k 的项集合为 Lk 中两个长度为 k-1 且有 k-2 元素相同的项集的并集。<br>Lk：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">apriori_gen</span><span class="params">(Lk, k)</span>:</span>  <span class="comment"># creates Ck。 Ck 包含 k 个项的集合，Lk 从 Ck 中提取出的频繁项集</span></div><div class="line">    ret_list = []</div><div class="line">    len_Lk = len(Lk)</div><div class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(len_Lk):</div><div class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> range(i + <span class="number">1</span>, len_Lk):</div><div class="line">            <span class="comment"># L1 = list(Lk[i])[:k-2]</span></div><div class="line">            <span class="comment"># L2 = list(Lk[j])[:k-2]</span></div><div class="line">            L1 = list(Lk[i])[:k<span class="number">-2</span>]</div><div class="line">            L2 = list(Lk[j])[:k<span class="number">-2</span>]</div><div class="line">            L1.sort()</div><div class="line">            L2.sort()</div><div class="line">            <span class="keyword">if</span> L1 == L2:</div><div class="line">                ret_list.append(Lk[i] | Lk[j])</div><div class="line">    <span class="keyword">return</span> ret_list</div></pre></td></tr></table></figure>
<h2 id="Mining-association-rules-from-frequent-item-sets"><a href="#Mining-association-rules-from-frequent-item-sets" class="headerlink" title="Mining association rules from frequent item sets"></a>Mining association rules from frequent item sets</h2><p>We quantified an itemset as frequent if it met our minimum support level. We have a similar measurement for association rules. This measurement is called the confidence. The confidence for a rule P ➞ H is defined as support(P | H)/ support(P).</p>
<p>We can observe that if a rule doesn ’ t meet the minimum confidence requirement, then subsets of that rule also won ’ t meet the minimum. Assume that the rule 0,1,2 ➞ 3 doesn ’ t meet the minimum confidence. We know that any rule where the left-hand side is a subset of {0,1,2} will also not meet the minimum confidence. We can use this property of association rules to reduce the number of rules weneed to test.</p>
<p>generateRules() is the main command, which calls the other two.<br>rulesFromConseq() generate a set of candidate rules.<br>calcConf() evaluate those rules.</p>
<h3 id="The-generate-rules-function"><a href="#The-generate-rules-function" class="headerlink" title="The generate_rules() function"></a>The <code>generate_rules()</code> function</h3><figure class="highlight python"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">generate_rules</span><span class="params">(L, support_data, min_conf=<span class="number">0.7</span>)</span>:</span></div><div class="line">    big_rule_list = []</div><div class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(<span class="number">1</span>, len(L)):</div><div class="line">        <span class="keyword">for</span> freqset <span class="keyword">in</span> L[i]:</div><div class="line">            H1 = [frozenset([item]) <span class="keyword">for</span> item <span class="keyword">in</span> freqset]</div><div class="line">            <span class="keyword">if</span> (i &gt; <span class="number">1</span>):</div><div class="line">                rules_from_conseq(freqset, H1, support_data, big_rule_list, min_conf)</div><div class="line">            <span class="keyword">else</span></div><div class="line">                calc_conf(freqset, H1, support_data, big_rule_list, min_conf)</div><div class="line">    <span class="keyword">return</span> big_rule_list</div></pre></td></tr></table></figure>
<p>It takes three inputs: a list of frequent itemsets, a dictionary of support data for those itemsets, and a minimum confidence threshold.<br>It ’ s going to generate a list of rules with confidence values that we can sort through later. These rules are stored in bigRuleList.<br>If no minimum confidence threshold is given, it ’ s set to 0.7. The other two inputs are the exact outputs from the apriori() function</p>
<p>This function loops over every frequent itemset in L and creates a list of single-item sets: H1 for each frequent itemset.<br><code>for i in range(1, len(L))</code> You start with the frequent itemsets that have two or more items because it ’ s impossible to create a rule from a single item.</p>
<p><code>rules_from_conseq()</code> If the frequent itemset has <em>more than two</em> items in it, then it could be considered for further merging. The merging is done with <code>rules_from_conseq()</code></p>
<p><code>calc_conf()</code> If the itemset only has two items in it, then you calculate the confidence with <code>calc_conf()</code>.</p>
<h3 id="The-calc-conf-function"><a href="#The-calc-conf-function" class="headerlink" title="The calc_conf function"></a>The <code>calc_conf</code> function</h3><figure class="highlight python"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">calc_conf</span><span class="params">(freqset, H, support_data, big_rule_list, min_conf=<span class="number">0.7</span>)</span>:</span></div><div class="line">    prunedH = []</div><div class="line">    <span class="keyword">for</span> conseq <span class="keyword">in</span> H:</div><div class="line">        conf = support_data[freqset] / support_data[freqset - conseq]</div><div class="line">        <span class="keyword">if</span> conf &gt;= min_conf:</div><div class="line">            print(freqset - conseq, <span class="string">'--&gt;'</span>, conseq, <span class="string">'conf:'</span>, conf)</div><div class="line">            big_rule_list.append((freqset - conseq, conseq, conf))</div><div class="line">            prunedH.append(conseq)</div><div class="line">    <span class="keyword">return</span> prunedH</div></pre></td></tr></table></figure>
<p>This function calculating the confidence of a rule and then finding out which rules meet the minimum confidence. You ’ ll return a list of rules that meet the minimum confidence; to hold this you create an empty list, prunedH.</p>
<p>Confidence(A -&gt; B): Support(A, B) / Support(A) &lt;==&gt; Confidence(freqset - conseq -&gt; conseq): Support(freqset) / Support(freqset - conseq)<br><code>conf = support_data[freqset] / support_data[freqset - conseq]</code>: Next, you iterate over all the itemsets in H and calculate the confidence.<br>If a rule does meet the minimum confidence, then the rule is returned and will be used in the next function, <code>rules_from_conseq()</code>. We fill them in the list big_rule_list, whichi is a parameter passed in.<br>此外满足最小置信度的规则中的 conseq 穿成列表，函数最终返回此列表。</p>
<h3 id="The-rules-from-conseq-function"><a href="#The-rules-from-conseq-function" class="headerlink" title="The rules_from_conseq() function"></a>The <code>rules_from_conseq()</code> function</h3><figure class="highlight python"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">def</span> <span class="title">rules_from_conseq</span><span class="params">(freqset, H, support_data, big_rule_list, min_conf)</span>:</span></div><div class="line">    m = len(H[<span class="number">0</span>])</div><div class="line">    <span class="keyword">if</span> (len(freqset) &gt; (m + <span class="number">1</span>)):</div><div class="line">        <span class="comment"># see if the frequent itemset is large enough to have subsets of size m + 1 removed; if so, you proceed.</span></div><div class="line">        Hmp1 = apriori_gen(H, m + <span class="number">1</span>)</div><div class="line">        Hmp1 = calc_conf(freqset, Hmp1, support_data, big_rule_list, min_conf)</div><div class="line">        <span class="keyword">if</span> (len(Hmp1) &gt; <span class="number">1</span>):</div><div class="line">            rules_from_conseq(freqset, Hmp1, support_data, big_rule_list, min_conf)</div></pre></td></tr></table></figure>
<p>To generate more association rules from our initial itemset, you use The <code>rules_from_conseq()</code> function. This takes a frequent itemset and H, which is a list of items that could be on the right-hand side of a rule ( 即所有可能的逻辑后件 ).<br>You use the <code>apriori_gen</code> function to generate combinations of the items in H without repeating. This is stored in Hmp1, which will be the H list in the next iteration. Hmp1 contains all the possible rules.<br> You want to see if any of these make sense by testing their confidence in <code>calc_conf()</code>. If more than one rule remains, then you recursively call <code>rules_from_conseq()</code> with Hmp1 to see if you could combine those rules further.</p>

      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2017/08/28/K-means-Clustering/" rel="next" title="K-Means Clustering">
                <i class="fa fa-chevron-left"></i> K-Means Clustering
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2017/08/30/dimensionality-reduction-techniques/" rel="prev" title="Dimensionality Reduction Techniques">
                Dimensionality Reduction Techniques <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          
  <div class="comments" id="comments">
    
  </div>


        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap" >
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
          <img class="site-author-image" itemprop="image"
               src="/uploads/avatar.jpg"
               alt="东木金" />
          <p class="site-author-name" itemprop="name">东木金</p>
           
              <p class="site-description motion-element" itemprop="description">正在学习机器学习，希望能变得很强！</p>
          
        </div>
        <nav class="site-state motion-element">

          
            <div class="site-state-item site-state-posts">
              <a href="/archives/">
                <span class="site-state-item-count">162</span>
                <span class="site-state-item-name">日志</span>
              </a>
            </div>
          

          
            
            
            <div class="site-state-item site-state-categories">
              <a href="/categories/index.html">
                <span class="site-state-item-count">18</span>
                <span class="site-state-item-name">分类</span>
              </a>
            </div>
          

          
            
            
            <div class="site-state-item site-state-tags">
              <a href="/tags/index.html">
                <span class="site-state-item-count">42</span>
                <span class="site-state-item-name">标签</span>
              </a>
            </div>
          

        </nav>

        

        <div class="links-of-author motion-element">
          
            
              <span class="links-of-author-item">
                <a href="https://github.com/bdmk" target="_blank" title="GitHub">
                  
                    <i class="fa fa-fw fa-github"></i>
                  
                    
                      GitHub
                    
                </a>
              </span>
            
              <span class="links-of-author-item">
                <a href="mailto:catcherchan94@outlook.com" target="_blank" title="E-Mail">
                  
                    <i class="fa fa-fw fa-envelope"></i>
                  
                    
                      E-Mail
                    
                </a>
              </span>
            
          
        </div>

        
        

        
        

        


      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#The-Apriori-principle"><span class="nav-number">1.</span> <span class="nav-text">The Apriori principle</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Finding-frequent-itemsets-with-the-Apriori-algorithm"><span class="nav-number">2.</span> <span class="nav-text">Finding frequent itemsets with the Apriori algorithm</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#Generating-candidate-itemsets"><span class="nav-number">2.1.</span> <span class="nav-text">Generating candidate itemsets</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#代码实现"><span class="nav-number">2.1.1.</span> <span class="nav-text">代码实现</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#the-full-Apriori-algorithm"><span class="nav-number">3.</span> <span class="nav-text">the full Apriori algorithm</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Mining-association-rules-from-frequent-item-sets"><span class="nav-number">4.</span> <span class="nav-text">Mining association rules from frequent item sets</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#The-generate-rules-function"><span class="nav-number">4.1.</span> <span class="nav-text">The generate_rules() function</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#The-calc-conf-function"><span class="nav-number">4.2.</span> <span class="nav-text">The calc_conf function</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#The-rules-from-conseq-function"><span class="nav-number">4.3.</span> <span class="nav-text">The rules_from_conseq() function</span></a></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright" >
  
  &copy;  2017 - 
  <span itemprop="copyrightYear">2018</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">东木金</span>
</div>


<div class="powered-by">
  由 <a class="theme-link" href="https://hexo.io">Hexo</a> 强力驱动
</div>

<div class="theme-info">
  主题 -
  <a class="theme-link" href="https://github.com/iissnan/hexo-theme-next">
    NexT.Gemini
  </a>
</div>


        

        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>

  
  <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  
  <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.2"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.2"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.2"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.2"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.2"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.2"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.2"></script>



  


  




	





  





  






  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'manual') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  

  

  

  
  
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="//cdn.bootcss.com/mathjax/2.7.1/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
  


  

  

</body>
</html>
